class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int nagetiveEnd = -1;
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] < 0){
                ++nagetiveEnd;
            }
            nums[i] = nums[i] * nums[i];
        }

        int nagetiveStart = 0;
        int positiveStart = nagetiveEnd + 1;
        int positiveEnd = nums.size() - 1;

        vector<int> rst;

        while((nagetiveStart <= nagetiveEnd) || (positiveStart <= positiveEnd)){
            if(nagetiveStart <= nagetiveEnd && positiveStart <= positiveEnd){
                if(nums[nagetiveEnd] < nums[positiveStart]){
                    rst.push_back(nums[nagetiveEnd]);
                    --nagetiveEnd;
                } else {
                    rst.push_back(nums[positiveStart]);
                    ++positiveStart;
                }
            } else if (nagetiveStart <= nagetiveEnd) {
                rst.push_back(nums[nagetiveEnd]);
                --nagetiveEnd;
            } else {
                rst.push_back(nums[positiveStart]);
                ++positiveStart;
            }
        }

        return rst;
    }
};

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        vector<int> rst(nums.size(), 0);
        int index = nums.size() - 1;

        while(left <= right){
            if(-nums[left] > nums[right]){
                rst[index] = nums[left] * nums[left];
                ++left;
            } else {
                rst[index] = nums[right] * nums[right];
                --right;
            }
            --index;
        }

        return rst;
    }
};